#include "stdio.h"
typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;
ListNode *midNode(ListNode*A)
{
    ListNode *fast=A,*slow=A;
    while (fast!=NULL&&fast->next!=NULL&&slow!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
ListNode* reverse(ListNode*A)
{
    if(A->next==NULL||A==NULL)
        return A;
    else
    {
        ListNode *newHead= reverse(A->next);
        A->next->next=A;
        A->next=NULL;
        return newHead;
    }
}
int chkPalindrome(ListNode* A)
{
    //0,1个节点
    if(A==NULL||A->next==NULL)
        return 1;
    if(A->next->next==NULL)//2个节点
    {
        if(A->val==A->next->val)
            return 1;
        else
            return 0;
    }
    //3个以上
    ListNode *mid= midNode(A);

    ListNode *p1=reverse(mid);//最后的节点
    ListNode *p2=A;//开头的节点
    while (p1!=NULL&&p2!=NULL)
    {
        if(p1->val!=p2->val)
            return 0;
        p1=p1->next;
        p2=p2->next;
    }
    return 1;
}
